package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;
import com.hqq.exercise.tree.TreeNodeUtil;

import java.util.Stack;

/**
 * FlattenToList 将二叉树拆成链表
 * 题目描述:
 * 将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的right指针，来表示链表中的next指针。
 * 样例输入:
 * ----1
 * ---/ \
 * --2   5
 * -/ \   \
 * 3   4   6
 * <p>
 * 样例输出:
 * -1
 * --\
 * ---2
 * ----\
 * -----3
 * ------\
 * -------4
 * --------\
 * ---------5
 * ----------\
 * -----------6
 * Created by heqianqian on 2017/9/12.
 */
public class FlattenToList {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode lChild = new TreeNode(2);
        TreeNode rChild = new TreeNode(5);
        lChild.left = new TreeNode(3);
        lChild.right = new TreeNode(4);
        rChild.right = new TreeNode(6);
        root.left = lChild;
        root.right = rChild;

        FlattenToList ftl = new FlattenToList();
        //ftl.flattenRecursion(root);
        //ftl.flattenLoop(root);
        ftl.flattenPreOrder(root);
        TreeNodeUtil.levelTraversal(root);
    }

    /**
     * 递归解法
     */
    public void flattenRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        /*使用DFS思路找到最左子节点*/
        if (root.left != null) {
            flattenRecursion(root.left);
        }
        if (root.right != null) {
            flattenRecursion(root.right);
        }
        /*把其父节点和右子节点断开，将原左子结点连上父节点的右子节点上*/
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = null;
        /*然后再把原右子节点连到新右子节点的右子节点上*/
        while (root.right != null) {
            root = root.right;
        }
        root.right = tmp;
    }

    /**
     * 循环解法
     */
    public void flattenLoop(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            //遍历节点 如果左节点不为空的话
            if (cur.left != null) {
                //找到左子树的最右节点 目的是把原右子树连接到该节点的右节点上
                TreeNode p = cur.left;
                while (p.right != null) {
                    p = p.right;
                }
                //断开当前节点和右子树 把左子树连接到当前节点的右节点 把原右子树连接到原左子树的最右节点的右子树上
                p.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            //当前节点为右子树的根节点 即原左子树的根节点
            cur = cur.right;
        }
    }

    /**
     * 前序迭代解法
     */
    public void flattenPreOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode tmp = stack.pop();
            if (tmp.left!=null){//如果当前节点的左子树非空
                TreeNode l = tmp.left;
                //找到左子树的最右节点
                while (l.right!=null){
                    l = l.right;
                }
                //断开当前节点和右子树 把左子树连接到右节点 右子树连接到原左子树的最右节点
                TreeNode r = tmp.right;
                tmp.right = tmp.left;
                tmp.left = null;
                l.right = r;
            }
            //把原左子树的根节点入栈
            if (tmp.right!=null){
                stack.push(tmp.right);
            }
        }
    }
}
